FPGAs may be used to implement large systems that include millions of gates and megabits of embedded memory. Of the tasks required in managing and optimizing a design, placement of components on the FPGAs and routing connections between components on the FPGA utilizing available resources can be the most challenging and time consuming. In order to satisfy placement and timing specifications, several iterations are often required to determine how components are to be placed on the target device and which routing resources to allocate to the components. The complexity of large systems often requires the use of EDA tools to manage and optimize their design onto physical target devices. Automated placement and routing algorithms in EDA tools perform the time consuming task of placement and routing of components onto physical devices.
Retiming is a synchronous circuit transformation that can optimize the speed-performance of a synchronous circuit. Retiming involves moving registers across combinational circuit elements in order to reduce the length of timing-critical paths. The combinational structure remains unchanged and the observable behavior of the circuit is identical to the original circuit. Retiming, however, has not been extensively used in commercial synthesis tools because it is difficult to generalize current retiming algorithms to handle complex issues such as multiple timing constraints, asynchronous conditions and architectural constraints. In addition, traditional retiming algorithms were very slow because binary searching was used to find a best retiming. For FPGA circuit netlists having n elements, retiming algorithms had in worst-case scenarios an n2 log(n) complexity. This was undesirable from a design standpoint.
Thus, what is needed is an efficient method and apparatus for performing retiming on FPGAs.